package com.demo.贪心算法;

import cn.hutool.core.lang.Console;

import java.util.Arrays;
import java.util.Objects;
import java.util.PriorityQueue;

/**
 * 动态中位数获取
 * @author cl
 */
public class DynamicMedian {
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> Integer.compare(o2, o1));

    public DynamicMedian(Integer... data) {
        Objects.requireNonNull(data);
        for (Integer num : data) {
            addAndGetMedian(num);
        }
    }

    public Integer addAndGetMedian(Integer addNum) {
        // 添加到小头堆
        if (minHeap.isEmpty()) {
            minHeap.add(addNum);
        } else {
            Integer tmp = minHeap.peek();
            // 弹出的大于等于的话直接加进去，小于的话放到大头堆
            if (addNum >= tmp) {
                minHeap.add(addNum);
            } else {
                maxHeap.add(addNum);
            }
            // 比较两个的大小
            if (Math.abs(maxHeap.size() - minHeap.size()) > 1) {
                if (minHeap.size() < maxHeap.size()) {
                    minHeap.add(maxHeap.poll());
                } else {
                    maxHeap.add(minHeap.poll());
                }
            }
        }
        return getMedian();
    }

    public Integer getMedian() {
        if (minHeap.size() < maxHeap.size()) {
            return maxHeap.peek();
        } else {
            return minHeap.peek();
        }
    }

    public static void main(String[] args) {
        Integer[] data = new Integer[]{12, 15, 16, 1, 7, 8, 10};
        DynamicMedian median = new DynamicMedian(data);
        Console.log("数据：{} 的中位数是：{}", Arrays.toString(data), median.getMedian());
        Console.log("数据：{} 添加 18 后中位数是：{}", Arrays.toString(data), median.addAndGetMedian(18));
        Console.log("数据：{} 添加 18, 11 后中位数是：{}", Arrays.toString(data), median.addAndGetMedian(11));
    }
}
